package day_7_6;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Main3 {
    /**
     * 239. 滑动窗口最大值
     * https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
     */

    /**
     * 堆
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        // 堆中的每一个节点对应的是 数组的下标的值 和 对应的下标
        PriorityQueue<int[]> q = new PriorityQueue<>((v1, v2) -> {
            return v1[0] != v2[0] ? v2[0] - v1[0] : v2[1] - v1[1];
        });

        // 先将前 k 个数组进行存入，之后堆中的最大值就是第一个滑动窗口中的最大值
        for(int i = 0;i < k;i++) {
            q.offer(new int[]{nums[i],i});
        }

        int[] ret =  new int[n - k + 1];
        ret[0] = q.peek()[0];
        for(int i = k;i < n;i++) {
            q.offer(new int[]{nums[i],i});
            // 判断当最大的值是否是当前滑动窗口中的最大值
            // 看这个下标是否是当前滑动窗口中的
            while(q.peek()[1] < i - k + 1) {
                // 出堆
                q.poll();
            }
            // 之后不论是出还是不出，都需要将最大值进行添加到数组中
            // 因为下标是从 k 开始的，所以对应的 ret下标 需要将k减去，进行还原
            ret[i- k + 1] = q.peek()[0];
        }
        return ret;
    }


    /**
     * 单调队列
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if(n == 0 || k == 0) {
            return new int[0];
        }

        Deque<Integer> deque = new LinkedList<>();
        int[] ret = new int[n - k + 1];
        for(int i = 1 - k,j = 0;j < n;j++,i++) {
            // 这样之后，[i,j] 区间就是滑动窗口
            // 先进行判断，这个互动窗口前面的值，是否和队列中的最大值是一样，也就是队列的头结点
            // 如果一致，说明这个最大值不是后面滑动窗口的值，应该将其进行出队列
            if(i > 0 && deque.peekFirst() == nums[i - 1]) {
                deque.removeFirst();
            }
            // 如果新入的值是大于队尾的数据，就将队尾的值出队列
            while(!deque.isEmpty() && deque.peekLast() < nums[j]) {
                deque.removeLast();
            }
            // 入队列，将新的数据
            deque.addLast(nums[j]);

            // 如果 i 这个数据是大于0了，说明已经出现滑动窗口了，将其进行统计最大值
            if(i >= 0) {
                ret[i] = deque.peekFirst();
            }
        }
        return ret;
    }
}
